// https://leetcode.cn/problems/factorial-trailing-zeroes/
// Created by ade on 2022/8/24.
//
#include <iostream>
#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    // 问题的本质是程式中包含多少个5
    int trailingZeroes(int n) {
        int num = 0;
        for (int i = 5; i <= n; i = i + 5) {
            int j = i;
            while (j > 0 && j % 5 == 0) {
                num++;
                j /= 5;
            }
        }
        return num;
    }

    // 优化后的方法
    int trailingZeroes(int n) {
        int num = 0;
        while (n) {
            num += n / 5;
            n = n / 5;
        }
        return num;
    }
};

int main() {
    Solution so;
    cout << so.trailingZeroes(15) << endl;
    return 0;
}